googologywikiaorg-20200223-history
User blog:Superiumentarius/Turing machine state reduction
This is an algorithm to reduce the number of states of a Turing machine using additional symbols. I will only show the algorithm for reducing the number of states to exactly three, but it can obviously me modified to allow for the reduction to more states (but not less than three) Given: TM with: :N states: :: q_0, q_1, ..., q_{N-1} :K symbols: :: S = \{A, B, C, ...\} :Initial state: :: q_0 Result: 3-state TM with the same behaviour as the original TM Algorithm: 1. Add (N-1)*2*K symbols: A_{k_U}, A_{k_D}, B_{k_U}, B_{k_D}, C_{k_U}, C_{k_D}, ... for 0 < k < N We need two new set of the original symbols for each state that gets removed. The index k shows which state this symbol will be used for. Each symbol is needed twice; once for counting upwards (U) and once for counting downwards (D) 2. Remove all states except for q_0 3. Add 2 new states q_L and q_R Definition of state q_R : Each of these lines is needed multiple times. Example for the first line: Definition of q_L is analogous to q_R with every 'Move' instruction set to 'R' and every transition to q_L set to q_R instead. Both of theses states are just used for counting. Whenever they encounter an 'upwards-counting' symbol (i.e. with index 'U') or a symbol of the original alphabet the index gets incremented, and vice-versa for downwards-counting symbols. 4. Add all instructions from the original states to q_0 by modifying them using the first of the following rules that is applicable: ( \{\alpha, \beta, \gamma, X, Z\} are variables, # can be anything) :4.1 Instruction in the form of: : :Can be added to q_0 without further modifications :4.2 Instruction in the form of: : :Replace with: : :4.3 Instruction in the form of: : :Replace with: : :4.4 Instruction in the form of: : :(Note: this is just a combination of 4.2 and 4.3) :Replace with: : How it works The only state that remains of the original TM is q_0 . Every time a transition to a removed state would happen, the TM instead writes a symbol with an index where the index represents the state we should currently be in. The transition state is dependend on whether the TM-head moved right or left(transition to q_R or q_L respectively). Example: Original instruction looks like this: Modified instruction: The 'D' in the subscript refers to 'downwards-counting' q_R will then read a symbol of the original alphabet, replace it with the same symbol with index 1 (this time with 'U' in the subscript), move left and transition to q_L . q_L decrements the index of the read symbol, moves right and transitions to q_R again. Repeat until the index of the symbol in the original cell gets decremented to 0. q_L then writes the corresponding symbol of the original alphabet in the cell, moves right and transitions to q_0 . Since the symbol in the adjacent cell now has the same index as the state the TM should be in, q_0 can now emulate this state. Overhead: Number of symbols increased from K to (N-1)*2*K Number of steps increases by a factor of about 2*(N-1) (worst case) Example http://morphett.info/turing/turing.html?2388a4e6f8846ce81025a80f08ec3911 This is a simple example of a reduction. The original 4-state TM replaces the first four '1's it encounters with an underscore and then halts. Category:Blog posts